1. Field of Invention
The present application is directed towards systems and methods for decoding barcodes.
2. Description of Related Art
Machine-readable symbols, often referred to as barcodes, are widely seen in daily life. They provide information about products, parcels, tickets, etc. One type of barcode is the one-dimensional (1D) barcode made up straight dark lines with varying widths and spaced at varying intervals. Information may be encoded in the width of the bars and the width of the spaces. FIG. 1 is an illustration of a meal ticket that includes a barcode. There exist a number of methods to locate and decode 1D and 2D barcodes.
One such method of decoding a barcode is described in U.S. Pat. No. 5,073,954 issued to Richard G. VAN TYNE et al. in which the barcode is located by summing the black pixels in segments with a predetermined width along each horizontal scan line. The location of a barcode is identified using L pattern characteristic found in histograms of barcode POSTNET images. Once a barcode region is located the black pixels are summed up for each vertical scan line. A threshold value proportional to the average maxima of these sums is used to determine the location and width of black bars producing a binary code. This barcode locating and decoding method was suitable for certain types of barcode such as the POSTNET code which contains full-height bars and half-height bars with known image width. This method also assumes the black pixels in the image are pre-determined before the barcode detection operation and the definition of black does not change.
A more general barcode decoding method that can be applied to all types of barcodes without requirement on bar width has been described in U.S. Patent Application No. 2006/0050961 issued to Mohanaraj THIYAGARAJAH. This method scans the image line-by-line without prior knowledge of the barcode location. Each horizontal scan-line is segmented into black or white pixel groups or tokens. This step is referred to as tokenization, which consists of converting image pixels to either black or white (non-black) and grouping continuous black or white pixels. Bars are represented by adjacent black pixels. Spaces are represented by adjacent white pixels. Bars may be denoted by zeroes and spaces by ones. The image of the current scan line is converted to an array of interlaced zeroes and ones. Every bar or space is a token. The width of each token is measured in units of image pixels and later used in the decoding step. This prior art method states that a method of adaptive thresholding may be used to distinguish black and white pixels from a grayscale image, but does not provide any details on how it might be implemented.
After tokenization barcode start or stop patterns are searched for in the sequence of tokens. If a pattern is found, multi-stage verification is carried out to verify that the detected signature pattern is correct and therefore can indicate presence of a barcode candidate.
Decoding may start once a signature pattern is verified. The goal is to generate codes from the tokens and look them up in a barcode dictionary. The decoding step stops before reaching the end of the token list when an erroneous code is generated or stop pattern or reversed start pattern is found.
Another method for decoding barcodes is described in U.S. Pat. No. 4,998,010 issued to Donald G. CHANDLER et al. This patent describes a method of detecting a barcode region by first using properties of spacing and directionality of the barcode. Frequency analysis is performed on an entire image in an attempt to find the region with barcode patterns. After the barcode region is found, a similar processing including tokenization and decoding is carried out inside the barcode region.
The print quality of a barcode depends on the printer, the paper, and the ink. The bars and spaces of the barcode may not have a uniform image intensity or color. This may be due to deterioration the paper or ink from use or folding. Stains may also change the intensity or color of some of the bars and spaces. When a barcode is printed on low quality paper the ink can easily spread changing widths of the bars and spaces. Tokens generated from such barcodes could have errors. Some of the token widths may be incorrect, or the number of tokens may be incorrect. Since the barcode location procedure does not require correct segmentation of all tokens in order to succeed, inaccuracies in tokenization may not be revealed until decoding is performed.
The above methods have trouble decoding barcodes of poor quality. The present invention is a method for correcting errors in the decoding step when the source data has errors.